package algorithm.difficult;

import java.util.*;

/**
 * 给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。
 * <p>
 * 再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。
 * <p>
 * 以数组形式返回对应查询的所有答案。
 */
public class MinInterval1851 {

    public static int[] minInterval(int[][] intervals, int[] queries) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            int len = right - left + 1;
            for (int i = left; i <= right; i++) {
                Integer integer = map.get(i);
                if (integer == null || integer > len) {
                    map.put(i, len);
                }
            }
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = map.getOrDefault(queries[i], -1);
        }
        return res;
    }

    public static void main(String[] args) {
        minInterval2(new int[][]{{2, 3}, {2, 5}, {1, 8}, {20, 25}}, new int[]{2,19, 5, 22});
    }

    public static int[] minInterval2(int[][] intervals, int[] queries) {
        int[] res = new int[queries.length];
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        //构造query数组的查询数字和下标的映射
        int[][] qs = new int[queries.length][0];
        for (int i = 0; i < queries.length; ++i) {
            qs[i] = new int[] {queries[i], i};
        }
        Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
        //intervals的下标
        int i = 0;
        //优先队列 int[0] 距离  int[1]右端点
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int[] q : qs) {
            //1 区间左端点<=x 进入队列
            while (i < intervals.length && intervals[i][0] <= q[0]) {
                pq.add(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
                i++;
            }
            //2.若优先队列不为空，且右端点小于x，直接弹出
            while (!pq.isEmpty() && pq.peek()[1] < q[0]) {
                pq.poll();
            }
            //3.如果此时，pq顶部元素不为空，即为query的答案
            if (!pq.isEmpty()) {
                res[q[1]] = pq.peek()[0];
            } else {
                res[q[1]] = -1;
            }
        }
        return res;
    }

}
